class main {
	private char[] c3;

	public boolean isInterleave(String s1, String s2, String s3) {
		if (s1.length() + s2.length() != s3.length())
			return false;
		char[] c1 = s1.toCharArray();
		char[] c2 = s2.toCharArray();
		c3 = s3.toCharArray();
		Boolean[][] dp1 = new Boolean[c1.length+1][c2.length+1];
		boolean b = this.f(c1, 0, c1.length, c2, 0, c2.length, dp1);
		if (b)
			return b;
		Boolean[][] dp2 = new Boolean[c2.length+1][c1.length+1];
		b = this.f(c2, 0, c2.length, c1, 0, c1.length, dp2);
		return b;
	}

	private boolean f(char[] c1, int s1, int e1, char[] c2, int s2, int e2, Boolean[][] dp1) {
		if (dp1[s1][s2] != null)
			return dp1[s1][s2];
		if (s1 == e1 && s2 == e2) {// 两个字符串都用尽, 空串==空串
			dp1[s1][s2] = true;
			return true;
		}
		int p3 = s1 + s2;
		if (s1 == e1) {// 串1用尽
			if (c3.length - p3 != c2.length - s2) {
				dp1[s1][s2] = false;
				return false;
			}
			for (int j = s2; j < e2; j++, p3++) {
				if (c2[j] != c3[p3]) {
					dp1[s1][s2] = false;
					return false;
				}
			}
			dp1[s1][s2] = true;
			return true;
		}
		if (s2 == e2) {
			if (c3.length - p3 != c1.length - s1) {
				dp1[s1][s2] = false;
				return false;
			}
			for (int j = s1; j < e1; j++, p3++) {
				if (c1[j] != c3[p3]) {
					dp1[s1][s2] = false;
					return false;
				}
			}
			dp1[s1][s2] = true;
			return true;
		}
		for (int i = s1 + 1; i <= e1; i++) {
			for (int j = s2 + 1; j <= e2; j++) {
				boolean b = true;
				int p = p3;
				for (int p1 = s1; p1 < i; p1++, p++) {
					if (c1[p1] != c3[p]) {
						b = false;
						break;
					}
				}
				if (!b) {
					continue;
				}
				for (int p2 = s2; p2 < j; p2++, p++) {
					if (c2[p2] != c3[p]) {
						b = false;
						break;
					}
				}
				if (!b) {
					continue;
				}
				b = this.f(c1, i, e1, c2, j, e2, dp1);
				if (b) {
					dp1[s1][s2] = true;
					return true;
				}
			}
		}
		dp1[s1][s2] = false;
		return false;
	}
}
